package leetcode;
import java.util.*;
/**
 * 51.N皇后
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 解释：如上图所示，4 皇后问题存在两个不同的解法
 *
 * 输入：n = 1
 * 输出：[["Q"]]
 */
public class Num_51 {
    List<String> inner = new ArrayList<>();
    List<List<String>> outter = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    public List<List<String>> solveNQueens(int n) {
        dfs(n);
        return outter;
    }

    private void dfs(int n) {
        //边界条件
        if(inner.size() == n){
            outter.add(new ArrayList<>(inner));
            return;
        }

        for (int i = 0; i < n; i++) {
            if(set.add(i)){
                String s = indexQ(n,i);
            }
        }
    }

    private String indexQ(int n, int i) {
        StringBuilder sb = new StringBuilder();
        for(int j = 0; j < n; j++){
            if(j == i){
                sb.append("Q");
            }else{
                sb.append(".");
            }
        }
        return sb.toString();
    }
}
